package cn.xkai.exercise.b;

/**
 * @description: 最小栈
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 * <p>
 * 实现 MinStack 类:
 * MinStack() 初始化堆栈对象。
 * void push(int val) 将元素val推入堆栈。
 * void pop() 删除堆栈顶部的元素。
 * int top() 获取堆栈顶部的元素。
 * int getMin() 获取堆栈中的最小元素。
 * @author: kaixiang
 * @date: 2022-07-13
 **/
public class Solution55 {
    /**
     * 链表头，相当于栈顶
     */
    private ListNode head;

    /**
     * 压栈，需要判断栈是否为空
     */
    public void push(int x) {
        if (empty()) {
            head = new ListNode(x, x, null);
        } else {
            head = new ListNode(x, Math.min(x, head.min), head);
        }
    }

    /**
     * 出栈，相当于把链表头删除
     */
    public void pop() {
        if (empty()) {
            throw new IllegalStateException("栈为空……");
        }
        head = head.next;
    }

    /**
     * 栈顶的值也就是链表头的值
     */
    public int top() {
        if (empty()) {
            throw new IllegalStateException("栈为空……");
        }
        return head.val;
    }

    /**
     * 链表中头结点保存的是整个链表最小的值，所以返回head.min也就是
     * 相当于返回栈中最小的值
     */
    public int getMin() {
        if (empty()) {
            throw new IllegalStateException("栈为空……");
        }
        return head.min;
    }

    /**
     * 判断栈是否为空
     */
    private boolean empty() {
        return head == null;
    }

    static class ListNode {
        public int val;
        public int min;//最小值
        public ListNode next;

        public ListNode(int val, int min, ListNode next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
}
